package com.zsj.heap;


/**
 * @Author zsj
 * @Version 1.0
 * @Date 2024/4/9 19:39
 * @Description
 */
public class HeapLeetCodeQuestion {
    public static void main(String[] args) {

        System.out.println(new HeapLeetCodeQuestion().findKthLargest(new int[]{3, 2, 3, 1, 2, 4, 5, 5, 6}, 4));
        System.out.println(new HeapLeetCodeQuestion().findKthLargest(new int[]{3, 2, 1, 5, 6, 4}, 2));
        System.out.println("=======================");
        System.out.println(new HeapLeetCodeQuestion().findKthLargest2(new int[]{3, 2, 3, 1, 2, 4, 5, 5, 6}, 4));
        System.out.println(new HeapLeetCodeQuestion().findKthLargest2(new int[]{3, 2, 1, 5, 6, 4}, 2));
    }

    /**
     * 215.数组中的第K个最大元素
     */
    public int findKthLargest(int[] nums, int k) {
        MaxHeap maxHeap = new MaxHeap(nums);
        int ans = 0;
        while (k != 0) {
            ans = maxHeap.poll();
            k--;
        }
        return ans;
    }


    public int findKthLargest2(int[] nums, int k) {
        MinHeap minHeap = new MinHeap(k);
        for (int i = 0; i < k; i++) {
            minHeap.offer(nums[i]);
        }
        for (int i = k; i < nums.length; i++) {
            if (nums[i] > minHeap.peek()) {
                minHeap.replace(nums[i]);
            }
        }
        return minHeap.peek();
    }

}

//295. 数据流的中位数
class MedianFinder {
    //使用大顶堆和小顶堆来解决这个问题

    public MedianFinder() {

    }

    public void addNum(int num) {

    }

    //返回所有元素的中位数
    public double findMedian() {
        return 0;
    }
}

/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder obj = new MedianFinder();
 * obj.addNum(num);
 * double param_2 = obj.findMedian();
 */